|
The Pólya enumeration theorem, also known as the Redfield–Pólya Theorem, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by John Howard Redfield in 1927. In 1937 it was independently rediscovered by George Pólya, who then greatly popularized the result by applying it to many counting problems, in particular to the enumeration of chemical compounds. The Pólya enumeration theorem can also be incorporated into symbolic combinatorics and the theory of combinatorial species. == A simplified, unweighted version == Let ''X'' be a finite set and let ''G'' be a group of permutations of ''X'' (or a finite symmetry group that acts on ''X''). The set ''X'' may represent a finite set of beads, and ''G'' may be a chosen group of permutations of the beads. For example, if ''X'' is a necklace of ''n'' beads in a circle, then rotational symmetry is relevant so ''G'' is the cyclic group ''Cn'', while if ''X'' is a bracelet of ''n'' beads in a circle, rotations and reflections are relevant so ''G'' is the dihedral group ''Dn'' of order ''2n''. Suppose further that ''Y'' is a finite set of colors — the colors of the beads — so that ''YX'' is the set of colored arrangements of beads (more formally: ''YX'' is the set of functions .) Then the group ''G'' acts on ''YX'' . The Pólya enumeration theorem counts the number of orbits under ''G'' of colored arrangements of beads by the following formula: : where is the number of colors and ''c''(''g'') is the number of cycles of the group element ''g'' when considered as a permutation of ''X''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Pólya enumeration theorem」の詳細全文を読む スポンサード リンク
|